package com.fr.lintcode;

import java.util.Stack;

import org.junit.Test;

public class Q1001 {

	/**
	 * @param asteroids
	 *            : a list of integers
	 * @return: return a list of integers
	 */
	public int[] asteroidCollision(int[] asteroids) {
		// write your code here
		Stack<Integer> stack = new Stack<>();
		for (int i : asteroids) {
			if (stack.isEmpty()) {
				stack.push(i);
			} else {
				while (!stack.isEmpty()) {
					int tmp = stack.peek();
					if (tmp * i < 0) {
						if(tmp < 0){
							stack.push(i);
							break;
						}
						if (Math.abs(tmp) == Math.abs(i)) {
							stack.pop();
							break;
						} else if (Math.abs(tmp) > Math.abs(i)) {
							break;
						} else {
							stack.pop();
							if(stack.isEmpty()){
								stack.push(i);
								break;
							}
						}
					} else {
						stack.push(i);
						break;
					}
				}
			}
		}
		if (stack.isEmpty()) {
			return new int[0];
		} else {
			int length = stack.size();
			int[] rs = new int[length];
			for (int i = length - 1; i >= 0; i--) {
				rs[i] = stack.pop();
			}
			return rs;
		}

	}

	@Test
	public void testAsteroidCollision() {
		int[] asteroids = { 3,-69,-65,67,-76,34,10,96,55,77,85,56,99,-1,6,-37,-7,-70,75,-60,4,-73,35,-32,3,-7,72,83,-82,70,68,63,33,-68,-100,61,-96,27,89,81,-11,-63,69,49,-34,23,87,23,26,-67,67,-100,-84,-89,-76,-42,-86,-96,86,7,25,9,-17,7,-15,-35,-65,-82,-32,90,-27,39,30,-42,-3,-71,-46,24,20,-84,8,51,-84,24,53,66,87,-64,27,-5,-68,86,-49,-53,68,21,-88,58,21,-18 };
		int[] rs = asteroidCollision(asteroids);
		System.out.println(rs);
	}

}
